package sort;

import java.util.Arrays;

public class QuickSort {

  public static void main(String[] args) {
    //int[] arr={56,7,213,0,-21,56,89,3,54,0};

    int arr[] = new int[80000000];
    for (int i = 0; i < 80000000; i++) {
      arr[i]= (int) (Math.random()*80000000);
    }
    long start=System.currentTimeMillis();
    quickSort(arr,0,arr.length-1);
    long now = System.currentTimeMillis();
    System.out.println(now-start);
    //System.out.println(Arrays.toString(arr));
  }

  public static void quickSort(int[] arr,int left,int right) {
    if (left>right){
      return;
    }
    int l=left;
    int r=right;
    int key=arr[left];
    int temp=0;
    while (l!=r){

    while (arr[r]>=key&&l<r){
      r--;
    }
    while (arr[l]<=key&&l<r){
      l++;
    }
    if (l<r){
      temp=arr[r];
      arr[r]=arr[l];
      arr[l]=temp;
    }

    }
    arr[left]=arr[l];
    arr[l]=key;
    quickSort(arr,left,l-1);
    quickSort(arr,r+1,right);
  }
}
